package 树;

public class Leedcode236二叉树的最近公共祖先 {
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果root == q 或者 root == 直接返回
        if (root == q || root == q){
            return root;
        }
        //走到这里说明至少存在三个节点，此时采用后序遍历
        lastOrder(root,p,q);
        return lca;
    }

    private boolean lastOrder(TreeNode root, TreeNode p, TreeNode q) {
        //递归终止条件，
        if (root == null){
            return false;
        }
        //从左子树中找，判断是否能够找到p或者q
        int left = lastOrder(root.left,p,q) ? 1 : 0;
        int right = lastOrder(root.right,p,q) ? 1 : 0;
        int mid = (root == p || root == q) ? 1 : 0;
        if((left + mid + right) > 2) {
            lca = root;
        }
        return (left + right + mid) > 0;
    }
}
